package com.lc.projects.structure.sort;

/***
 * 基数排序：分成0-9十个桶，依次从最低比较到最高，放到对应的桶，直到最高位。取出来 就是排好序的位置。
 * 
 * @author user
 *
 */
public class RadixSort {
	public static int[] sort(int[] nums, int range) {
		int k = 0; //
		int n = 1;// 计算位数的时候用
		int bit = 1; // 控制根据哪一位排序

		int[][] temp = new int[10][nums.length];
		// 由于这里控制每个数字出现了多少次，所以对于二维数组，只会取对应0-9的位置出现的次数（count[0]）个数字，多于的舍去了，所以有不需要的数据并不影响
		int[] count = new int[10]; // 存放该位出现多少次

		while (bit <= range) {
			for (int i = 0; i < nums.length; i++) {
				// 计算出来该位置的数值
				int value = (nums[i] / n) % 10;
				// 放到临时数组对应的位置
				temp[value][count[value]] = nums[i];
				//
				count[value]++;
			}

			for (int i = 0; i < count.length; i++) {
				if (count[i] != 0) {
					for (int j = 0; j < count[i]; j++) {
						nums[k] = temp[i][j];
						k++;
					}
				}
				count[i] = 0;
			}

			n *= 10;
			k = 0;
			bit++;

		}

		return nums;
	}
}
